/*
// 快速排序，A 是数组，n 表示数组的大小
quick_sort(A, n) {
  quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数，p,r 为下标
quick_sort_c(A, p, r) {
  if p >= r then return
  
  q = partition(A, p, r) // 获取分区点
  quick_sort_c(A, p, q-1)
  quick_sort_c(A, q+1, r)
}
//原地优化
partition(A, p, r) {
  pivot := A[r]
  i := p
  for j := p to r-1 do {
    if A[j] < pivot {
      swap A[i] with A[j]
      i := i+1
    }
  }
  swap A[i] with A[r]
  return i
*/
#include <iostream>

using namespace std;


int partition(int* A, int p, int r){
	int pivot = A[r];
	int i = p;
	for( int j=p;j<r;++j){
		if(A[j] < pivot){
			swap(A[i],A[j]);
			++i;
		}
	}
	swap(A[i],A[r]);

	return i;
}
void quick_sort_c(int* A, int p, int r){
	if(p>=r)
		return;
	int q = partition(A,p,r); 
	quick_sort_c(A, p, q-1);
	quick_sort_c(A, q+1, r);
}
void quick_sort(int* A, int n){
	quick_sort_c(A, 0, n-1);
}
//给一数组a[1…n]，选出其中第K小(大)的那个数。时间复杂度要求 O(nlogn).
//直接在排序时给出第K值的时间复杂度是 O(n)
int main(){
	int rank = 3;
	int count = 7;
	int A[count]= {-4,2,10,9,8,7,6};
	//验证
	int B[count]= {1,2,3,4,5,6,7};
	int C[count]= {8,7,6,5,4,3,2};
	int D[count]= {1,1,1,1,1,1,1}; //这种情况怎么算？

	int *R = B;
	for(int i=0;i<count;++i){
		cout<< R[i];
	}
	
	quick_sort(R,count);

	for(int i=0;i<count;++i){
		cout<< R[i];
	}
	cout << endl;
	cout << "The "<< rank <<"th smallest is "<< R[rank-1]<< endl; 
	return 0;
}









